|
In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm of making decisions in some decision processes, most notably employed in game playing. The leading example of its use is in contemporary computer Go programs,〔(【引用サイトリンク】title=MCTS.ai: Everything Monte Carlo Tree Search )〕 but it is also used in other board games, as well as real-time video games and non-deterministic games such as poker (see history section). == Principle of operation == MCTS concentrates on analysing the most promising moves, basing the expansion of the search tree on random sampling of the search space. MCTS in games is based on many ''playouts''. In each playout, the games are played-out to the very end by selecting moves at random. The final game result of each playout is then used to weight the nodes in the game tree so that better nodes are more likely to be chosen in future playouts. The most primitive way of using playouts is playing the same number of them after each legal move of the current player and choosing the move, after which the most playouts ended up in the player's victory. The efficiency of this method—called ''Pure Monte Carlo Game Search''—often increases when, as time goes on, more playouts are assigned to the moves that have frequently resulted in the player's victory (in previous playouts). Full MCTS consists in employing this principle recursively on many depths of the game tree. Each round of MCTS consists of four steps: * ''Selection'': starting from root , select successive child nodes down to a leaf node . The section below says more about a way of choosing child nodes that lets the game tree expand towards most promising moves, which is the essence of MCTS. * ''Expansion'': unless ends the game, either create one or more child nodes of it and choose from them node . * ''Simulation'': play a random playout from node . * ''Backpropagation'': using the result of the playout, update information in the nodes on the path from to . Sample steps of one round are shown in the figure below. Each tree node stores the number of won/played playouts. Note that the updating of the number of wins in each node during backpropagation should be from the point of view of the player who made the move that resulted in that node 〔http://mcts.ai/code/python.html〕 (this is not accurately reflected in the sample image above). This ensures that during selection, each player chooses to expand towards the most promising moves for that player, which mirrors the maximizing behavior of each player in reality. Such rounds are repeated as long as the time allotted to a move is not up. Then, one of moves from the root of the tree is chosen but it is the move with the most simulations made rather than the move with the highest average win rate. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Monte Carlo tree search」の詳細全文を読む スポンサード リンク
|